package com.lwt.codetop.linkedLists;

// 23. 合并 K 个升序链表

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 思路：链表的k路归并排序，有多个链表，每次我们要选择首节点最小的节点加入结果集
 *      如何知道k个指针指向的节点，哪个最小呢？ ---> 小根堆 ---> 每次拿到k个链表中最小的节点
 *
 */
public class MergekSortedLists {
    public static void main(String[] args) {
        // 构建测试用例--->创建k个有序链表
        ListNode list1 = createList(new int[]{1, 4, 5}); // 通过数组构建链表 1->4->5->null
        ListNode list2 = createList(new int[]{1, 3, 4});
        ListNode list3 = createList(new int[]{2, 6});

        // 加入链表数组
        ListNode[] lists = new ListNode[]{list1, list2, list3};

        // 合并
        ListNode res = mergeKLists(lists);
        while (res != null){
            System.out.print(res.val + " ");
            res = res.next;
        }

    }

    /**
     * 合并k个升序链表
     * @param lists
     * @return
     */
    private static ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        //1. 定义一个小根堆，将所有链表的头指针放入，比较依据是它们的值
        PriorityQueue<ListNode> q = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        //简化版：PriorityQueue<ListNode> q = new PriorityQueue<ListNode>((x,y) -> (x.val - y.val));

        //2. k个链表的头指针(头指针对应的节点)加入小根堆
        for (int i = 0; i < lists.length; i++) {
            if(lists[i] != null){
                q.add(lists[i]);
            }
        }
        //3. 归并k个有序链表
        while(!q.isEmpty()){
            // 拿到k个链表中最小的节点
            ListNode t = q.poll();
            cur.next = t;
            // 当前链表的下一个节点加入堆中，为下一次做准备
            if(t.next != null) q.add(t.next);
            // 指针移动
            cur = cur.next;
        }
        return dummy.next;
    }

    /**
     * 辅助方法：基于数组快速构建链表
     * @param nums
     * @return
     */
    private static ListNode createList(int[] nums) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        for (int num : nums) {
            cur.next = new ListNode(num);
            cur = cur.next;
        }
        return dummy.next;
    }
}
